//给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 
//
// 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 
//
// 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。 
//
// 
//
// 示例 1： 
//
// 
//输入：[7,1,5,3,6,4]
//输出：5
//解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
//     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
// 
//
// 示例 2： 
//
// 
//输入：prices = [7,6,4,3,1]
//输出：0
//解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= prices.length <= 105 
// 0 <= prices[i] <= 104 
// 
// Related Topics 数组 动态规划 
// 👍 1948 👎 0

package com.cute.leetcode.editor.cn;
public class BestTimeToBuyAndSellStock {
    public static void main(String[] args) {
        Solution solution = new BestTimeToBuyAndSellStock().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 一刷的贪心算法
         * 1.直接遍历：从后向前遍历
         *  遍历的过程中进行最高售价的更新以及当前价格和售价之间产生收益的更新
         */
        public int maxProfit(int[] prices) {
            int len = prices.length;
            if (len<=1) return 0;
            int max = prices[len-1];
            int res = 0;
            for (int i = len-2; i >=0 ; i--) {
                if (prices[i]<max) res = Math.max(res, max-prices[i]);
                else max = Math.max(prices[i],max);
            }
            return res;
        }

        /**
         * 二刷的贪心算法
         */
        public int maxProfitTwoGreedy(int[] prices) {
            int min = prices[0];
            int res = 0;
            for (int price : prices){
                res = Math.max(res, price-min);
                min = Math.min(min, price);
            }
            return res;
        }

        /**
         * 2.题解中有动态规划的方法进行实现的
         *   买卖股票有约束，根据题目意思，有以下两个约束条件：
         *   条件 1：你不能在买入股票前卖出股票
         *   条件 2：最多只允许完成一笔交易
         *   因此 当天是否持股 是一个很重要的因素，而当前是否持股和昨天是否持股有关系
         *   为此我们需要把 是否持股 设计到状态数组中。
         *
         *   推导状态转移方程：
         * dp[i][0]：规定了今天不持股，有以下两种情况：
         *  昨天不持股，今天什么都不做；
         *  昨天持股，今天卖出股票（现金数增加），
         *
         * dp[i][1]：规定了今天持股，有以下两种情况：
         *  昨天持股，今天什么都不做（现金数与昨天一样）；
         *  昨天不持股，今天买入股票（注意：只允许交易一次，因此手上的现金数就是当天的股价的相反数）。
         *
         */
        public int maxProfit2(int[] prices) {
            int len = prices.length;
            // 特殊判断
            if (len < 2) {
                return 0;
            }
            int[][] dp = new int[len][2];

            // dp[i][0] 下标为 i 这天结束的时候，不持股，手上拥有的现金数
            // dp[i][1] 下标为 i 这天结束的时候，持股，手上拥有的现金数

            // 初始化：不持股显然为 0，持股就需要减去第 1 天（下标为 0）的股价
            dp[0][0] = 0;
            dp[0][1] = -prices[0];

            // 从第 2 天开始遍历
            for (int i = 1; i < len; i++) {
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
                dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
            }
            return dp[len - 1][0];
        }

        /**
         * 二刷：一开始是用的贪心算法，没想起来dp怎么写
         * 现在定义dp[i][0]表示持股最大现金数，dp[i][1]表示不持股最大现金数
         * 可以用滚动数组来优化空间
         */
        public int maxProfitTwo(int[] prices) {
            int[][] dp = new int[prices.length][2];
            dp[0][0] = -prices[0];
            dp[0][1] = 0;
            for (int i = 1; i < prices.length; i++) {
                dp[i][0] = Math.max(dp[i-1][0],- prices[i]);
                dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0] + prices[i]);
            }
            return dp[prices.length-1][1];//一定是不持股的时候赚钱多
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}